219D - Choosing Capital for Treeland - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

void findMinReversals(vector<vector<pair<int, int>>> &adjList, vector<bool> &visited, int src, int level, int &rootAns, int &minRes, int oneCount, vector<int> &minNodes){

    visited[src] = true;
    int val = level-2*oneCount;
    if(val < minRes){
        minRes = val;
        minNodes.clear();
        minNodes.push_back(src);
    }
    else if(val == minRes){
        minNodes.push_back(src);
    }

    for(auto p: adjList[src]){
        if(!visited[p.first]){
            rootAns += p.second;
            findMinReversals(adjList, visited, p.first, level+1, rootAns, minRes, oneCount + p.second, minNodes);
        }
    }
}

int main(){


    int n;
    cin >> n;

    vector<vector<pair<int, int>>> adjList(n+1);
    
    for(int i = 1; i <= n-1; i++){
        int u, v;

        cin >> u >> v;

        adjList[u].push_back({v, 0});
        adjList[v].push_back({u, 1});
    }

    vector<bool> visited(n+1, false);
    int minRes = INT_MAX;
    vector<int> minNodes;
    int rootAns = 0;
    findMinReversals(adjList, visited, 1, 0, rootAns, minRes, 0, minNodes);
    sort(minNodes.begin(), minNodes.end());

    cout << rootAns + minRes << endl;

    for(int node: minNodes){
        cout << node << " ";
    }
    return 0;
}